
using System;
using System.Diagnostics;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace Ack
{
	public class SnesEncoder
	{
		private static int EncodeRowDifferences(byte[] input, byte[] output, int patternIndex, int referenceIndex, bool flipx, bool flipy)
		{
			int len = 0;
			output[len++] = 0; // header 1 (reserved for RD scheme)
			output[len++] = 0; // header 2 (set bit = row is explicitly stored)
			
			if(flipx) output[0] |= 0x80;
			
			for(int y = 0; y < 8; ++y)
			{
				byte refByte = (byte)(input[referenceIndex*8+(flipy?7-y:y)]);
				if(flipx) refByte = Misc.ReverseByte(refByte);
				
				if(input[patternIndex*8+y] != refByte)
				{
					output[len++] = input[patternIndex*8+y];
					output[1] |= (byte)(1 << (7-y));
				}
			}
			
			return len;
		}
		
		private static byte[] EncodeRD(byte[] input, int patternIndex, out bool flipy)
		{
			int lowestCost = Int32.MaxValue;
			int bestIndex = -1;
			byte[] testRD = new byte[10];
			byte[] bestRD = new byte[10];
			int bestRDLength = 0;
			
			flipy = false;

			for(int i = 0; i <= 127; ++i)
			{
				int referenceIndex = patternIndex-(i+1);
				
				if(referenceIndex < 0)
					break;
	
				for(int f = 0; f < 4; ++f)
				{
					int len = EncodeRowDifferences(input,testRD,patternIndex,referenceIndex,(f&1)!=0,(f&2)!=0);
					
					if(len < lowestCost)
					{
						lowestCost = len;
						testRD.CopyTo(bestRD,0);
						bestRDLength = len; 
						bestIndex = i;
						flipy = (f&2)!=0;
					}
				}
			}
			
			if(bestRDLength>0)
			{
				bestRD[0] |= (byte)bestIndex;
				
				return Misc.TrimArray(bestRD,bestRDLength);
			}
			
			return null;
		}
		
		public static byte[] GetTransposed8x8(byte[] input, int patternIndex)
		{
			byte[] output = new byte[8];
			for(int y = 7; y >= 0; --y)
			{
				byte outRow = 0;
				outRow |= (byte)(((input[patternIndex*8+0] >> y) & 1) << 7);
				outRow |= (byte)(((input[patternIndex*8+1] >> y) & 1) << 6);
				outRow |= (byte)(((input[patternIndex*8+2] >> y) & 1) << 5);
				outRow |= (byte)(((input[patternIndex*8+3] >> y) & 1) << 4);
				outRow |= (byte)(((input[patternIndex*8+4] >> y) & 1) << 3);
				outRow |= (byte)(((input[patternIndex*8+5] >> y) & 1) << 2);
				outRow |= (byte)(((input[patternIndex*8+6] >> y) & 1) << 1);
				outRow |= (byte)(((input[patternIndex*8+7] >> y) & 1) << 0);
				output[7-y] = outRow;				
			}
			
			return output;
		}
		
		private static byte[] EncodeRowRepeats(byte[] input, int patternIndex)
		{
			List<byte> output = new List<byte>();
			output.Add(0);
			output.Add(input[0]);
			
			for(int y = 1; y < 8; ++y)
			{
				byte row = input[patternIndex*8+y];
				if(row != input[patternIndex*8+y-1])
				{
					output.Add(row);
					output[0] |= (byte)(1 << (7-y));
				}
			}
			
			return output.ToArray();
		}
		
		private static byte[] EncodeRCR(byte[] input, int patternIndex)
		{
			byte[] output = EncodeRowRepeats(input,patternIndex);
			byte[] outputT = EncodeRowRepeats(GetTransposed8x8(input,patternIndex),0);

			// Select the transpose if it take less bytes.
			// If so, also set bit 7 in the RCR header.
			if(outputT.Length < output.Length)
			{
				output = outputT;
				output[0] |= 0x80;
			}
			
			return output;
		}

		private static void GetTwoMostCommonPatterns(byte[] input, out ulong patternA, out ulong patternB)
		{
			int patternCount = input.Length / 8;
			Debug.Assert((input.Length & 7) == 0);
			
			Dictionary<ulong, int> freqs = new Dictionary<ulong, int>();
			for(int pi = 0; pi < patternCount; ++pi)
			{
				byte[] temp = Misc.TrimArray(input,pi*8,8);
				ulong key = BitConverter.ToUInt64(temp,0);
				if(!freqs.ContainsKey(key))
					freqs.Add(key,1);
				else
					freqs[key]++;
			}

			var topTwo = (from entry in freqs orderby entry.Value descending select entry.Key).Take(2).ToArray();

			patternA = topTwo[0];
			patternB = topTwo[1];
		}
		
		enum PatternMode
		{
			Raw					= 0, // pattern is stored raw (8 bytes)
			RCR					= 1, // pattern uses row/column-repeat encoding (1+n bytes)
			CommonA				= 2, // the two most common patterns in an 8KB block are found and signaled via this mode
			CommonB				= 3, // the two most common patterns in an 8KB block are found and signaled via this mode

			// Illegal for first pattern:
			SameAsLast			= 4, // pattern is equal to the preceding one (note: can span 2bit tiles)
			SameAsLastInverted	= 5, // this is fairly common between bitplanes of the same tile
			
			RD		= 6, 
			RD2     = 7  // pattern is based on reference pattern + differing rows (2+n bytes)
		};

		public class Statistics
		{
			public int _totalPatternCount;
			public int _groupRepeatCount;
			public int[] _patternModeCounts = new int[] {0,0,0,0,0,0,0,0};
			public Dictionary<int,int> _countsPerOffset = new Dictionary<int, int>();

			public override string ToString()
			{
				string s = "";
				s += "\nCommonA: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.CommonA]/_totalPatternCount);
				s += "\nCommonB: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.CommonB]/_totalPatternCount);
				s += "\nSameAsLast: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.SameAsLast]/_totalPatternCount);
				s += "\nSameAsLastInverted: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.SameAsLastInverted]/_totalPatternCount);
			//	s += "\nSameAsTwoBack: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.SameAsTwoBack]/_totalPatternCount);
				s += "\nRD: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.RD]/_totalPatternCount);
				s += "\nRCR: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.RCR]/_totalPatternCount);
				s += "\nRaw: " + String.Format("{0:0%}",(float)_patternModeCounts[(int)PatternMode.Raw]/_totalPatternCount);
				//s += "\nRepeated groups: " + _groupRepeatCount;
				return s;
			}
		};
		
		public static List<byte> Encode(byte[] input, Statistics stats)
		{
			List<byte> output = new List<byte>();
			int patternCount = input.Length / 8;
			Debug.Assert((input.Length & 7) == 0);
			
			ulong patternA, patternB;
			GetTwoMostCommonPatterns(input, out patternA, out patternB);

			output.AddRange(BitConverter.GetBytes(patternA));
			output.AddRange(BitConverter.GetBytes(patternB));
			
			stats._totalPatternCount += patternCount;
			
			int groupHeaderStart = 0;
			for(int pi = 0; pi < patternCount; ++pi)
			{
				byte[] patternBytes = Misc.TrimArray(input,pi*8,8);
				ulong pattern = BitConverter.ToUInt64(patternBytes.ToArray(),0);

				int indexInGroup = pi & 7;
				
				// Start of 8 pattern group?
				if(indexInGroup == 0)
				{
					// Add empty group header
					groupHeaderStart = output.Count;
					output.Add(0);
					output.Add(0);
					output.Add(0);
				}
				
                Action<byte> writePatternMode = delegate(byte bits)
                {
                        byte mask = (byte)(1 << (7-indexInGroup));
                        output[groupHeaderStart+0] &= (byte)~mask;
                        output[groupHeaderStart+1] &= (byte)~mask;
                        output[groupHeaderStart+2] &= (byte)~mask;
                        output[groupHeaderStart+0] |= (byte)((((int)bits & 4) != 0) ? mask : (byte)0);
                        output[groupHeaderStart+1] |= (byte)((((int)bits & 2) != 0) ? mask : (byte)0);
                        output[groupHeaderStart+2] |= (byte)((((int)bits & 1) != 0) ? mask : (byte)0);
                };
				
				// PatternMode.Common
				{
					if(pattern == patternA)
					{
						writePatternMode((byte)(PatternMode.CommonA));
						stats._patternModeCounts[(int)PatternMode.CommonA]++;
						continue;
					}

					if(pattern == patternB)
					{
						writePatternMode((byte)(PatternMode.CommonB));
						stats._patternModeCounts[(int)PatternMode.CommonB]++;
						continue;
					}
				}
				
				// PatternMode.SameAsLast
				// PatternMode.SameAsLastInverted
				if(pi > 0)
				{
					ulong patternPrev = BitConverter.ToUInt64(Misc.TrimArray(input,pi*8-8,8),0);

					if(pattern == patternPrev)
					{
						writePatternMode((byte)PatternMode.SameAsLast);
						stats._patternModeCounts[(int)PatternMode.SameAsLast]++;
						continue;
					}
					
					if(pattern == ~patternPrev)
					{
						writePatternMode((byte)PatternMode.SameAsLastInverted);
						stats._patternModeCounts[(int)PatternMode.SameAsLastInverted]++;
						continue;
					}					
				}

				// PatternMode.SameAsTwoBack
				/*if(pi > 1)
				{
					ulong patternPrev2 = BitConverter.ToUInt64(input.GetRange(pi*8-16,8).ToArray(),0);
					
					if(pattern == patternPrev2)
					{
						writePatternMode((byte)PatternMode.SameAsTwoBack);
						stats._patternModeCounts[(int)PatternMode.SameAsTwoBack]++;
						continue;
					}
				}*/
				

				// 1) Row-Repeat encoded tile
				//
				// Remove repeated rows. Store which ones are explicit as 1's in a 1 byte tile header.
				//
				// RCR Header: T1234567
				// 		T: Tile is transposed				
				// 		1-7: Row numbers that are explicit (note: row 0 is always stored)		
				byte[] rcr = EncodeRCR(patternBytes,0);
			
				
				// 6-7) Row Difference encoding, find "best" earlier pattern and store differing rows.
				// 
				// RD header: xppppppp  (x=unused, p=pattern offset)
				//            01234567  0-7: Rows that are stored (n=# bits set)
				// Then follow "n" stored rows.
				bool rdflipy;
				byte[] rd = EncodeRD(input, pi, out rdflipy);
				if(rd != null && rd.Length > 0 && rd.Length < rcr.Length)
				{
					if(rdflipy)
						writePatternMode((byte)(PatternMode.RD+1));
					else
						writePatternMode((byte)(PatternMode.RD));

					stats._patternModeCounts[(int)PatternMode.RD]++;
					output.AddRange(rd);
					continue;
				}
				else if(rcr.Length < 8) // 8 is the cost of a raw pattern
				{
					writePatternMode((byte)(PatternMode.RCR));
					stats._patternModeCounts[(int)PatternMode.RCR]++;
					output.AddRange(rcr);
					continue;
				}
				
				// 0) Fallback: raw encoded tile
				writePatternMode((byte)(PatternMode.Raw));
				stats._patternModeCounts[(int)PatternMode.Raw]++;
				output.AddRange(patternBytes);
			}
			
			
			
			return output;
		}
	
		
	}
}
